﻿using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{ /*Задание 6
 Написать реализацию алгоритма для выполнения следующего:
В выражении ((((1 ? 2) ? 3) ? 4) ? 5) ? 6 вместо каждого знака ? вставить знак одной из 4 арифметических операций +, –, *, / так, чтобы результат вычислений равнялся заданному целому числу N (при делении дробная часть отбрасывается).
 Результатом выполнения алгоритма является число, показывающее количество различных решений задачи. Если решений нет, вернуть 0.
 По желанию пользователя данного алгоритма все верные последовательности операций (верные выражения) выводить на консоль.
 Крайне желательно использование автоматического юнит-тестирования для данного задания.

Пример:
Вход  Выход  Дополнительно
21    4      ((((1+2)+3)+4)+5)+6
             ((((1*2)+3)*4)-5)+6
             ((((1*2)-3)+4)*5)+6
             ((((1*2)*3)+4)+5)+6
28    0      решений нет*/

    public class Test
    {

        public static void Main(String[] args)
        {
            int X = 21;

            Console.WriteLine(solve(X, 6, true));
        }

        public static int solve(int X, int N, bool printPath)
        {
            ArrayList operations = new ArrayList();
            return solveInner(X, N, printPath, operations, 1, 2); // 1 is the first number
        }

        public static int solveInner(int X, int N, bool printPath, ArrayList operations, int curX, int nextOperand)
        {
            if (operations.Count == N - 1)
            {
                if (curX == X)
                {
                    if (printPath)
                    {
                        Console.Write("CORRECT PATH: ");
                        foreach (int elem in operations)
                        {
                            Console.Write(elem + " ");
                        }
                        Console.WriteLine();
                    }
                    return 1;
                }

                return 0;
            }

            int res = 0;

            nextOperand = nextOperand + 1;

            operations.Add(1);
            res = res + solveInner(X, N, printPath, operations, curX + nextOperand, nextOperand); // plus
            operations.RemoveAt(operations.Count - 1); // remove last

            operations.Add(2);
            res = res + solveInner(X, N, printPath, operations, curX - nextOperand, nextOperand); // minus
            operations.RemoveAt(operations.Count - 1); // remove last

            operations.Add(3);
            res = res + solveInner(X, N, printPath, operations, curX * nextOperand, nextOperand); // multiple
            operations.RemoveAt(operations.Count - 1); // remove last

            operations.Add(4);
            res = res + solveInner(X, N, printPath, operations, curX / nextOperand, nextOperand); // delete
            operations.RemoveAt(operations.Count - 1); // remove last

            return res;
        }
    }
}
